package demo;

import java.util.Arrays;

public class QuickSort {

    public static void swap(int[]arr,int i,int j){
         int temp=arr[i];
         arr[i]=arr[j];
         arr[j]=temp;
    }
    public static int parttion(int[]arr,int fromIdx,int toIdx){

        int leftIdx=fromIdx;
        int rightIdx=toIdx;
        int pivot=arr[toIdx];
        while(leftIdx<rightIdx){

            while(leftIdx<rightIdx && arr[leftIdx]<=pivot){
                 leftIdx++;
            }
            while(leftIdx<rightIdx && arr[rightIdx]>=pivot){
                rightIdx--;
            }
            swap(arr,leftIdx,rightIdx);//交换左右
        }
        swap(arr,leftIdx,toIdx);//最后交换基准值
        return leftIdx;
    }
    public static void quickSort(int[]arr,int fromIdx,int toIdx){
        if(toIdx-fromIdx<=1){
            return ;
        }
        int pivotIdx=parttion(arr,fromIdx,toIdx);
        quickSort(arr,fromIdx,pivotIdx-1);
        quickSort(arr,pivotIdx+1,toIdx);
    }
    public static void main(String[] args) {
        int[] arr={1,5,8,1,-1,0};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}
